/*******************************************************************************
    Project: JobShop Problem using Genetic Algorithm: Serial Approach
    File: crossover.cpp
    Author: Ameya Deswandikar
    Email: ameya.des1@gmail.com
    Revision: 0.1
    Date & Time: 11/08/2013

    Description:
    This file implements the crossover and mutation functions
*******************************************************************************/

/*
** ----------------------------------------------------------------------------
** S Y S T E M   I N C L U D E S
** ----------------------------------------------------------------------------
*/
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <cstring>
#include <ctime>
#include <cassert>

/*
** ----------------------------------------------------------------------------
** C O M P O N E N T   I N C L U D E S
** ----------------------------------------------------------------------------
*/
#include "crossover.h"
#include "types.h"

using namespace std;

unsigned int rand_seeds[MAX_THREADS][10];

// Crossover percentage
extern float crossover;

/*
** ----------------------------------------------------------------------------
** P T H R E A D S   B A R R I E R   V A R I A B L E S
** ----------------------------------------------------------------------------
*/

// Mutex for Barrier
extern pthread_mutex_t   crossoverSyncLock;

// Conditional Variable for Barrier
extern pthread_cond_t    crossoverSyncCV;

//Counter for threads
extern int crossoverSyncCount;

extern int crossovernT;
extern int crossoverCount;
extern int crossoverRemainder;

cs_arg_struct args[MAX_THREADS];

/*============================================================================
**
** Function Name:       crossoverBarrier
**
** Description:         The barrier function for crossover.
**
** Invocation:          main
**
** Input Parameters:    None
**
** Return Values:       Nothing
**
**==========================================================================*/
void crossoverBarrier()
{
    int ret;

    pthread_mutex_lock(&crossoverSyncLock);

    crossoverSyncCount++;

    if(crossoverSyncCount == crossovernT)
    {
        ret = pthread_cond_broadcast(&crossoverSyncCV);
        assert(ret == 0);
        crossoverSyncCount=0;                //Reset the SyncCount after counting all threads
    }
    else
    {
        ret = pthread_cond_wait(&crossoverSyncCV, &crossoverSyncLock);
        assert(ret == 0);
    }
    pthread_mutex_unlock(&crossoverSyncLock);
}


/*============================================================================
**
** Function Name:       GenNewPop
**
** Description:         Generates the population per thread
**
** Invocation:          GeneratePopulation
**
** Input Parameters:    void* tmp: data needed for each thread to create
** 						population. cs_arg_struct
**
** Return Values:       void*
**
**==========================================================================*/
void* GenNewPop(void *tmp)
{
	cs_arg_struct *data;

	data = (cs_arg_struct *)tmp;

	//Variables
	long int threadID = (long int)data->tid;
	long unsigned int start = threadID * crossoverCount;

	if(threadID <= crossoverRemainder)
		start += threadID;
	else
		start += crossoverRemainder;

	long unsigned int end = start + crossoverCount - 1;

	if(threadID < crossoverRemainder)
		end++;

	crossoverBarrier();

	string parent1,parent2;

	int njobs = data->jobs;
	int nmachines = data->machines ;
	int len_crossover =  njobs * nmachines * crossover;

	unsigned int x = 0;
	unsigned int y = 1;

	for(unsigned int a = start; a <= end; a++)
	{
		// Choose from the top half of the sorted population.
		x = rand_r(&rand_seeds[threadID][RS_CR_NEW_POP_X]) % (crossoverCount / 2);
		y = rand_r(&rand_seeds[threadID][RS_CR_NEW_POP_Y]) % (crossoverCount / 2);

		while(x == y)
		{
			y = rand_r(&rand_seeds[threadID][RS_CR_NEW_POP_Y]) % (crossoverCount / 2);
		}

		parent1 = data->SortedPopulation[x].Chromosome;
		parent2 = data->SortedPopulation[y].Chromosome;
		data->NewPopulation[a].Chromosome = CrossOver(parent1,parent2,len_crossover,njobs,nmachines,threadID);
	}

	return NULL;
}



/*============================================================================
**
** Function Name:       CreateNewPopulation
**
** Description:         Creates new population from the sorted population,
** 						Parents are chosen from first half
**
** Invocation:          main
**
** Input Parameters:    Individual OldPop[] : Old Population
** 						int population 		: population size
** 						Individual *NewPop  : New population
** 						int NumJobs    		: Number of Jobs
** 						int NumMachines		: Number of machines
** 						float crossover		: crossover fraction (0 to 1)
** 						unsigned int numThreads: Number of threads
**
** Return Values:       int
**
**==========================================================================*/
int CreateNewPopulation(Individual OldPop[],int population,Individual *NewPop,
						int NumJobs,int NumMachines, float crossover, unsigned int numThreads)
{

	//Threading variables
	pthread_t* Threads;
	pthread_attr_t attr;

	int ret;
	long int ThreadID = 0;

	crossovernT = numThreads;

	//Counters
	crossoverCount = (population) / numThreads;
	crossoverRemainder = (population) % numThreads;

	//Initialize the threads
	Threads = (pthread_t *) malloc(sizeof(pthread_t) * numThreads);
	assert(Threads != NULL);

	pthread_attr_init(&attr);
	pthread_attr_setscope(&attr,PTHREAD_SCOPE_SYSTEM);

	//Initialize Mutex
	ret = pthread_mutex_init(&crossoverSyncLock,NULL);
	assert(ret == 0);

	//Initialize Condition Variable
	ret = pthread_cond_init(&crossoverSyncCV,NULL);
	assert(ret == 0);
	crossoverSyncCount = 0;

	//Creating Threads
	for(ThreadID = 0; ThreadID < numThreads; ThreadID++)
	{
		args[ThreadID].tid = ThreadID;
		args[ThreadID].NewPopulation = NewPop;
		args[ThreadID].SortedPopulation = OldPop;
		args[ThreadID].jobs = NumJobs;
		args[ThreadID].machines = NumMachines;
		ret = pthread_create(&Threads[ThreadID], &attr, GenNewPop,(void*)(&args[ThreadID]));
		assert(ret==0);
	}

	//Joining Threads
	for(ThreadID = 0;ThreadID < numThreads; ThreadID++)
	{
		ret = pthread_join(Threads[ThreadID],NULL);
		assert(ret==0);
	}

	// Cleanup
	pthread_mutex_destroy(&crossoverSyncLock);
	pthread_cond_destroy(&crossoverSyncCV);
	pthread_attr_destroy(&attr);

	if (Threads)
		delete[] Threads;

	return 0;

}


/*============================================================================
**
** Function Name:       RouletteSelection
**
** Description:         Selects the individuals to mate biased to the best fitness
** 						using a biased roulette wheel algorithm
**
** Invocation:          CreateNewPopulation
**
** Input Parameters:    int TotalFitness : Total fitness (Circumference of roulette wheel)
** 						Individual *Popu : Population array to choose from
** 						int Population   : Population size
**
** Return Values:       string : The biased selected individual chromosome
**
**==========================================================================*/

string RouletteSelection(int TotalFitness,Individual *Popu,int Population)
{
    float rand_num=((float)rand_r(&rand_seeds[0][RS_ROULETTE])/(RAND_MAX));
    float Slice = (float)(rand_num * TotalFitness);
    float FitnessSoFar = 0.0f;
    string tempchromsome;
    for (int i=0; i<Population; i++)
	{
		FitnessSoFar += Popu[i].Fitness;

		//if the fitness so far > random number return the chromo at this point
		if (FitnessSoFar >= Slice)
        {
#ifdef __debug__
            cout << "I am here" << endl;
#endif
            tempchromsome = Popu[i].Chromosome;
#ifdef __debug__
            cout << Popu[i].Chromosome;
            cout << tempchromsome;
#endif
            break;
        }
	}
    return tempchromsome;
}

/*============================================================================
**
** Function Name:       CrossOver
**
** Description:         Generates an offspring individual from parents by
** 						crossing over some genes from the donor and implanting
** 						them in the parent. Chooses a random crossover point in
** 						the donor, computes the insertion point in the parent from
** 						the spliced donor sequence, mutates and creates a offspring
**
** Invocation:          CreateNewPopulation
**
** Input Parameters:    const string& parent: Parent chromosome
				 	 	const string& donor: Donor Chromosome
				 	 	unsigned int len_crossover: Number of implanted genes from donor
				 	 	unsigned int numJobs: Number of jobs
				 	 	unsigned int numMachines: Number of machines
				 	 	long int threadID: The thread ID (for random seed)
**
** Return Values:       string : The new offspring
**
**==========================================================================*/
string CrossOver(const string& parent,
				 const string& donor,
				 unsigned int len_crossover,
				 unsigned int numJobs,
				 unsigned int numMachines,
				 long int threadID)
{
	string offspring;
	unsigned int len_chr = parent.length();

	gene* combinedChromosome = new gene[len_chr + len_crossover];

	/*
	 * STEP 1:
	 * Generate a combined chromosome containing part of donor
	 * genes included in the parent gene.
	 */

	GetCombinedChromosome(parent, donor, len_crossover, combinedChromosome,numMachines,threadID);

	/*
	 * STEP 2:
	 * Repair the combined chromosome by deleting genes from parent
	 * that match the name and index of implanted genes from donor
	 */

	offspring = RepairCombinedChromosome(combinedChromosome, len_chr + len_crossover, numJobs,
									len_crossover);

	if(combinedChromosome)
			delete[] combinedChromosome;

	return offspring;
}

/*============================================================================
**
** Function Name:       GetCombinedChromosome
**
** Description:         Generate a combined chromosome containing part of donor
** 						genes included in the parent gene.
**
** Invocation:          CrossOver
**
** Input Parameters:    const string& parent: Parent chromosome
						const string& donor : Donor chromosome
						unsigned int len_crossover : number of crossed over genes
						gene* combined : Combined genes array aka chromosome
						unsigned int numMachines : Number of machines
						long int threadID: The thread ID for random seed
**
** Return Values:       Nothing
**
**==========================================================================*/
void GetCombinedChromosome(const string& parent,
						   const string& donor,
						   unsigned int len_crossover,
						   gene* combined, unsigned int numMachines,
						   long int threadID)
{
	string offspring;
	unsigned int len_chr = parent.length();
	unsigned int i;
	unsigned int l;

	// Randomly choose a crossover point in the donor
	//srand(time(NULL));
	unsigned int crossover_point = rand_r(&rand_seeds[threadID][RS_CROSSOVER]) % len_chr;

	unsigned int insertion_point = 0;
	char cutChrStartGene;

	// Store the positions (indexes) of the genes. Use this for marking deletions later.
	unsigned int* parentPos = new unsigned int [parent.length()];
	unsigned int* donorPos = new unsigned int [donor.length()];

	// Arrays to keep track of the position counts during the traversal
	unsigned int* genePosParent = new unsigned int [numMachines];
	unsigned int* genePosDonor = new unsigned int [numMachines];

	// Initialize arrays to zero
	memset(genePosParent,0,sizeof(unsigned int) * numMachines);
	memset(genePosDonor,0,sizeof(unsigned int) * numMachines);

	// Obtain indices for parent
	for (i = 0; i < parent.length(); i++)
	{
		genePosParent[parent[i] - 'A']++;
		parentPos[i] = genePosParent[parent[i] - 'A'];
	}

	// Obtain indices for donor
	for (i = 0; i < donor.length(); i++)
	{
		genePosDonor[donor[i] - 'A']++;
		donorPos[i] = genePosDonor[donor[i] - 'A'];
	}

#ifdef __debug__

	cout << endl << "Length of crossover string = " << len_crossover << endl;
	cout << endl << "Crossover point in donor (Starts with zero) = " << crossover_point << endl;

#endif

	// If crossover point makes implant genes wraps around the donor,
	// then no need to consider insertion point for parent. The donor genes
	// will simply wrap around the parent
	if(len_chr - crossover_point < len_crossover)
	{
		unsigned int first_donor_part_end_index = len_crossover - (len_chr - crossover_point + 1);

		// Copy first part of the donor
		// Cannot delete these genes
		for(i = 0; i <= first_donor_part_end_index; i++)
		{
			combined[i].name = donor[i];
			combined[i].canDelete = false;
			combined[i].pos = donorPos[i];
		}

		// Copy the whole parent
		for(i = 0; i < len_chr; i++)
		{
			combined[first_donor_part_end_index + i + 1].name = parent[i];
			combined[first_donor_part_end_index + i + 1].canDelete = true;
			combined[first_donor_part_end_index + i + 1].pos = parentPos[i];
		}

		// Now copy the end part of the donor
		l = 0;
		for(i = crossover_point; i < len_chr; i++)
		{
			combined[first_donor_part_end_index + len_chr + l + 1].name = donor[i];
			combined[first_donor_part_end_index + len_chr + l + 1].canDelete = false;
			combined[first_donor_part_end_index + len_chr + l + 1].pos = donorPos[i];
			l++;
		}

	}
	// Else if donor's crossover part does not wrap around donor,
	// then insert the implant genes at insertion point for parent
	else
	{
		// Compute the insertion point for parent
		cutChrStartGene = donor[crossover_point];
		insertion_point = GetInsertionPoint(parent, parentPos, cutChrStartGene, donorPos[crossover_point]);

#ifdef __debug__
		cout << "Insertion point in parent (Starts with zero) = " << insertion_point << endl;
#endif
		//Copy parent genes till the insertion point
		for(i = 0; i < insertion_point; i++)
		{
			combined[i].name = parent[i];
			combined[i].canDelete = true;
			combined[i].pos = parentPos[i];
		}

		// Copy the implant genes from donor
		// Cannot delete these genes
		l = 0;
		for(i = insertion_point; i < insertion_point + len_crossover; i++)
		{
			combined[i].name = donor[l + crossover_point];
			combined[i].canDelete = false;
			combined[i].pos = donorPos[l + crossover_point];
			l++;
		}

		// Copy the rest of the parent
		l = 0;
		for(i = insertion_point; i < len_chr; i++)
		{
			combined[insertion_point + len_crossover + l].name = parent[i];
			combined[insertion_point + len_crossover + l].canDelete = true;
			combined[insertion_point + len_crossover + l].pos = parentPos[i];
			l++;
		}
	}


#ifdef __debug__

		cout << endl << "Combined string format: <Gene> : <donor=0, parent=1> : <index>" << endl;
		cout << "Combined string is: ";

		// Print the combined chromosome
		for(i = 0; i < len_chr + len_crossover; i++)
		{
			cout << combined[i].name << ":" << combined[i].canDelete << ":" << combined[i].pos << "  ";
		}
		cout << endl;
#endif
		if(donorPos)
			delete[] donorPos;

		if(parentPos)
			delete[] parentPos;

		if(genePosParent)
			delete[] genePosParent;
		if(genePosDonor)
			delete[] genePosDonor;


}



/*============================================================================
**
** Function Name:       GetInsertionPoint
**
** Description:         Computes the insertion point in the parent
**
** Invocation:          CrossOver
**
** Input Parameters:    const string& parent : Parent
** 						unsigned int* parentPos : Array of positions of parent genes
** 						unsigned char cutChrStartGene : Spliced Start gene of donor implant
** 						unsigned int cutChrStartGenePos: Starting position of gene implant
**
** Return Values:       unsigned int: The insetion point
**
**==========================================================================*/
unsigned int GetInsertionPoint(const string& parent, unsigned int* parentPos, unsigned char cutChrStartGene, unsigned int cutChrStartGenePos)
{
	unsigned int insertion_point = 0;

	unsigned int i = 0;
	for(i = 0; i < parent.length(); i++)
	{
		if((parent[i] == cutChrStartGene) && (parentPos[i] == cutChrStartGenePos))
		{
			insertion_point = i + 1;
			break;
		}
	}

	return insertion_point;
}


/*============================================================================
**
** Function Name:       RepairCombinedChromosome
**
** Description:         Repairs the combined chromosome by deleting genes from parent
** 						that match the name and index of implanted genes from donor
**
** Invocation:          CrossOver
**
** Input Parameters:    gene* combinedChromosome : The array of parent + implanted genes
** 						unsigned int len : 		 : Total length of parent genes + implanted genes
** 						unsigned int numJobs	 : Num Jobs
						unsigned int len_crossover: Number of implanted genes
**
** Return Values:       string: The repaired chromosome
**
**==========================================================================*/

string RepairCombinedChromosome(gene* combinedChromosome, unsigned int len, unsigned int numJobs,
								unsigned int len_crossover)
{
	string repairedChromosome;
	unsigned int i = 0;
	unsigned int j = 0;
	unsigned int l = 0;

	// Maintain gene count for each gene type (gene is a job)
	unsigned int* implantGeneCount = new unsigned int [numJobs];

	gene* implantGenes = new gene [len_crossover];

	// Separate out implanted genes in an array
	l = 0;
	for(i = 0; i < len; i++)
	{
		if(!combinedChromosome[i].canDelete)
		{
			implantGenes[l] = combinedChromosome[i];
			l++;
		}
	}

	// Now mark for deletion each parent gene which is in the implanted gene
	//std::cout << std::endl;

#ifdef __debug__
	cout << "Genes marked for deletion: <name:index> = ";
#endif

	for(i = 0; i < len_crossover; i++)
	{
		for(j = 0; j < len; j++)
		{
			if(combinedChromosome[j].canDelete && combinedChromosome[j].name == implantGenes[i].name && combinedChromosome[j].pos == implantGenes[i].pos)
			{
#ifdef __debug__
				cout << combinedChromosome[j].name << ":" << combinedChromosome[j].pos << " ";
#endif
				combinedChromosome[j].name = '-';

			}
		}
	}


#ifdef __debug__
	cout << endl;
#endif

#ifdef __debug__
	cout << "Removed Genes: " ;
#endif

	// Now remove the genes and produce the offspring
	for(i = 0; i < len; i++)
	{
#ifdef __debug__
		cout << combinedChromosome[i].name << " ";
#endif

		if(combinedChromosome[i].name != '-')
		{
			repairedChromosome += combinedChromosome[i].name;
		}
	}

#ifdef __debug__
	cout << endl;
#endif

	if(implantGeneCount)
		delete[] implantGeneCount;

	if (implantGenes)
		delete[] implantGenes;

	return repairedChromosome;
}



/*============================================================================
**
** Function Name:       validateChromosome
**
** Description:         Checks if the chromosome is valid, for number and order
** 						of the genes.
**
** Invocation:          CrossOver
**
** Input Parameters:    const string& chr : The chromosome
** 						unsigned int numJobs : Number of Jobs
** 						unsigned int numMachines : Number of machines
**
** Return Values:       TRUE if valid chromosome, FALSE otherwise
**
**==========================================================================*/

bool validateChromosome(const string& chr, unsigned int numJobs, unsigned int numMachines)
{
	// Easiest check. Remember: Number of tasks = number of machines
	if(chr.length() != numJobs * numMachines)
		return false;

	unsigned int i = 0;

	// Default. Optimistic.
	bool isValid = true;

	// Array to store counts of tasks for each job
	unsigned int * totalTasks = new unsigned int [numJobs];

	// Initialize to zero
	memset(&totalTasks[0],0,sizeof(unsigned int) * numJobs);

	for(i = 0; i < chr.length(); i++)
	{
		totalTasks[chr[i] - 'A']++;
	}

	for(i = 0; i < numJobs; i++)
	{
		if(totalTasks[i] != numMachines)
			isValid = false;
	}

	if(totalTasks)
		delete[] totalTasks;

	return isValid;
}
